package 简单.模拟;

/**
 * 给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ：
 * <p>
 * nums[0] = 0
 * nums[1] = 1
 * 当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
 * 当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1]
 * 返回生成数组 nums 中的 最大 值。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/get-maximum-in-generated-array
 */
public class 获取生成数组中的最大值_1646 {

    public static void main(String[] args) {

        System.out.println(efficientGetMaximumGenerated(7));

    }

    //模拟算法，直接根据题目条件写运算过程
    public int getMaximumGenerated(int n) {
        if (n == 0) {
            return 0;
        }
        int[] nums = new int[n + 1];
        nums[0] = 0;
        nums[1] = 1;
        int max = 1;
        for (int i = 2; i < nums.length; i++) {
            if (i % 2 == 0) {
                nums[i] = nums[i / 2];
                max = Math.max(nums[i], max);
            } else {
                nums[i] = nums[(i - 1) / 2] + nums[(i - 1) / 2 + 1];
                max = Math.max(nums[i], max);
            }
        }
        return max;
    }

    /**
     * 优化，可以将两种情况合并，i/2=(i-1)/2，因为其自动向下取值
     * 当i为偶数时，i%2==0
     * nums[i]=nums[i/2]+i%2*nums[i/2+1]
     */
    public static int efficientGetMaximumGenerated(int n) {
        if (n == 0) {
            return 0;
        }
        int[] nums = new int[n + 1];
        nums[0] = 0;
        nums[1] = 1;
        int max = 1;
        for (int i = 2; i < nums.length; i++) {
            nums[i] = nums[i / 2] + i % 2 * nums[i / 2 + 1];
            max = Math.max(nums[i], max);
        }
        return max;
    }

}
